The effects of thermal substrate pretreatment on the growth of Au-catalyzed ZnO nanostructures by pulsed laser deposition are investigated. C-plane sapphire substrates are annealed prior to deposition of a thin Au layer. Subsequent ZnO growths on substrates annealed above 1,200°C resulted in a high density of nanosheets and nanowires, whereas lower temperatures led to low nanostructure densities. Separate Au film annealing experiments at 700°C showed little variation in the size and density of the Au catalyst droplets with substrate annealing temperature. The observed variation in the density of nanostructures is attributed to the number of surface nucleation sites on the substrate, leading to a competition between nucleation promoted by the Au catalyst and surface nucleation sites on the rougher surfaces annealed below 1,200°C.